package com.lintcode.solution;

public class Solution_28 {
    public static void main(String[] args) {
        int[][] a = { { 1, 3, 5, 7 }, { 10, 11, 16, 20 }, { 23, 30, 34, 50 } };
        Solution_28 solution = new Solution_28();
        System.out.println(solution.searchMatrix(a, 7));
    }
    
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int length = matrix[ i ].length;
            if ((i >= 1 && (target > matrix[ i - 1 ][ matrix[ i - 1 ].length - 1 ] && target < matrix[ i ][ 0 ])) ||
                i == 0 && target < matrix[ i ][ 0 ]) {
                return false;
            }
            if (target >= matrix[ i ][ 0 ] && target <= matrix[ i ][ length - 1 ]) {
                for (int j : matrix[ i ]) {
                    if (target == j) {
                        return true;
                    }
                }
            }
        }
        return false;
    }
}
